package LeetCode1_100;

import java.util.ArrayList;
import java.util.List;

/**
 * 求子集操作
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 思路 : 求子集，就是迭代数组，每个元素都有两种情况，选择 与 不选择
 *
 * 可以使用位运算， 集合中的每个元素，都可以选择，或者不选 ， 这样就可以按位与 操作完成， 假设nums=[1,2,3,4]，二进制的0可以写成0000，
 *              代表一个数也不取，1=0001表示去第一个数也就是[1]，2=0010，表示取第二个数[2]，3=0011表示取1和2位[1,2]，4=0100表示[3]....15=1111表示[1,2,3,4]
 *
 * 还可以用回溯的方式，表示选择与不选择两种情况， 这道题就用位运算考察.
 */
public class LeetCode78 {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < (1<<nums.length); i++) {    // num，length 数组左移一位的目的是，因为原数组范围是 2^n-1,   而 n位数组的可能情况是 2^n,所以要左移一位，能够遍历到所有情况
            List<Integer> sub = new ArrayList<>();
            for (int j = 0; j < nums.length ; j++) {
                if(((i>>j)&1) == 1){    // 按位运算，选中就添加，不选中就跳过
                    sub.add(nums[j]);
                }
            }
            res.add(sub);
        }
        return res;
    }

    public static void main(String[] args) {

    }
}
